package algorithm.shipinke;

/**
 * 1分、2分、5分硬币,数量不限,组合1元钱的数量
 * 注意这题不是DP题,因为不是找最优解
 * 找 1*X+2*Y+5*Z=100 所有可行的正整数解
 */


public class CoinCombine {

    public int coinCombination(int total) {
        int totalSolution = 0;

        for (int i = 0; i <= 20; i++) {
            for (int j = 0; j <= 50; j++) {
                if (100-5*i-2*j >= 0) totalSolution++;
                else break;
            }
        }
        return totalSolution;
    }

    public static void main(String[] args) {
        CoinCombine coinCombine = new CoinCombine();
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            coinCombine.coinCombination(100);
        }
        System.out.println(System.currentTimeMillis()-t1);
    }

}
